Conclusion

We think evaltrace notation is an effective tool for teaching the key concepts of evaluation in Lisp and other applicative languages. We also find that evaltrace is flexible—extensions to other features of Lisp such as tail-recursion elimination and first-class continuations (CALL/CC) are quite easy to make, though we have not included them here.

Because tracing has been a part of Lisp since the days of Lisp 1.5, we should point out how evaltrace diagrams differ from earlier tracing schemes. Lisp tracing programs usually work by replacing the body of the function to be traced; thus they are only able to show the APPLY part of the evaluation process. This can lead to ambiguities. For example, the functions FOO1 and FOO2 produce identical traces in most Lisp implementations:

$\begin{code} (defun bar (y) y) \strut (defun baz (z) z) \strut (defun foo1 (x) ... ...1: (BAZ 3) 1: returned 3 1: (BAR 3) 1: returned 3 0: returned 3 3 \end{code}$

In both cases, BAZ is invoked before BAR. But in the first case BAZ is computing the argument to BAR, while in the second case the calls to BAZ and BAR are independent. This difference is clearly portrayed in the corresponding evaltrace diagrams.

$\begin{evaltrace} +--> ;(foo1 3) \vert +**> ;Apply FOO1 to 3 * +--> ;(bar (baz x... ...AR to 3 * * * +_*> ;Result of BAR is 3 +_*> ;Result of FOO2 is 3 \end{evaltrace}$

Another notation for explaining some aspects of Lisp evaluation is the ``fence'' notation of Winston and Horn [6]. Fence notation focuses on the static structure of lexical contours; it is not concerned with the dynamic process of evaluation, function invocation, and return. While it can represent the environment of a closure as a series of nested fences, it cannot represent the application of closures, nor does it cover macro expansion. Like most Lisp TRACE notations, fence notation has no way to represent the difference between FOO1 and FOO2 above.

We believe evaltrace notation offers a significant improvement over both earlier notations, in terms of scope of coverage, graphical intuitiveness, and extensibility. Extensions for tail recursion elimination, first-class continuations, assignment, and multiple closures with a shared parent contour are discussed in [5]. We hope that both Lisp novices and educators find the notation to be as useful as we have. In support of this, we have made available a set of L^ATEX macros for producing evaltrace diagrams similar to the ones in this paper. They are available via anonymous ftp in compressed tar format, from a.ergo.cs.cmu.edu (128.2.250.219), in directory pub/evaltrace, files README and evaltrace.tar.Z.